// https://leetcode.cn/problems/design-add-and-search-words-data-structure/
// Created by ade on 2022/9/5.
// 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
//
//实现词典类 WordDictionary ：
//
//WordDictionary() 初始化词典对象
//void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
//bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
//
#include <iostream>
#include <vector>
#include <string>


using namespace std;

class WordDictionary {
public:
    vector<WordDictionary *> children;
    bool isEnd;

    WordDictionary() : children(26), isEnd(false) {}

    void addWord(string word) {
        WordDictionary *node = this;
        for (auto i : word) {
            if (!node->children[i - 'a'])
                node->children[i - 'a'] = new WordDictionary();
            node = node->children[i - 'a'];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        WordDictionary *node = this;
        return searchPrefix(node, word, 0);
    }

    bool searchPrefix(WordDictionary *node, const string &word, int index) {
        if (!node) return false;
        if (index == word.size()) {
            return node->isEnd;
        }
        if (word[index] == '.') {
            for (int i = 0; i < 26; i++) {
                if (node->children[i] && searchPrefix(node->children[i], word, index + 1)) {
                    return true;
                }
            }
        } else {
            return node->children[word[index] - 'a'] &&
                   searchPrefix(node->children[word[index] - 'a'], word, index + 1);
        }
        return false;
    }
};

int main() {
//    ["WordDictionary","addWord","addWord","addWord","addWord","search","search","addWord","search","search","search","search","search","search"]
//    [[],["at"],["and"],["an"],["add"],   ["a"],[".at"],  ["bat"], [".at"],["an."],  ["a.d."],["b."],["a.d"],["."]]
//    [null,null,null,null,null,false,false,null,true,false,false,false,true,false]
//    [null,null,null,null,null,false,false,null,true,true, false,false,true,false]
    WordDictionary w;
    w.addWord("at");
    w.addWord("and");
    w.addWord("an");
    w.addWord("add");

    cout << w.search("a") << endl;
//    cout << w.search("a") << endl;
//    cout << w.search("aa") << endl;
//    w.search("a");
//    w.search(".a");
//    w.search("a.");
    return 0;
}